#include <iostream>
#include <vector>
using namespace std;

typedef int* nPtr;

pair<nPtr , size_t> SortMinHeapTree(int *arr1, int *arr2, int sz1, int sz2)
{
	size_t NewArrNum = sz1 + sz2;
	nPtr pTempArr = new int[NewArrNum]();

	for (int i = 0, leftIndex = i, rightIndex = i;
		i < NewArrNum;
		++i)
	{
		if ((arr1[leftIndex] < arr2[rightIndex] && leftIndex < sz1) || rightIndex >= sz2)
		{
			pTempArr[i] = arr1[leftIndex];
			++leftIndex;
		}
		else
		{
			pTempArr[i] = arr2[rightIndex];
			++rightIndex;
		}
	}
	delete[] arr1;
	delete[] arr2;
	return{ pTempArr, NewArrNum };
}

pair<nPtr, size_t> MegerSort(vector<nPtr> &vec, int Left, int Right)
{
	if (Left == Right)
		return{vec[Left], 7};
	int mid = (Right + Left)/2;
	auto p1 = MegerSort(vec, Left, mid);
	auto p2 = MegerSort(vec, mid + 1, Right);

	auto Temp = SortMinHeapTree(p1.first, p2.first, p1.second, p2.second);
	return Temp;
}

int main()
{
	int *arr1 = new int[7]{11, 12, 13, 16, 21, 27, 42};
	int *arr2 = new int[7]{ 2, 12, 13, 27, 31, 36, 92 };
	int *arr3 = new int[7]{ 1, 7, 12, 32, 36, 53, 91 };
	int *arr4 = new int[7]{ 3, 6, 11, 22, 37, 42, 90 };
	int *arr5 = new int[7]{ 3, 6, 11, 22, 37, 42, 90 };
	int *arr6 = new int[7]{ 3, 6, 11, 22, 37, 42, 90 };

	vector<nPtr>ptrVec;
	ptrVec.emplace_back(arr1);
	ptrVec.emplace_back(arr2);
	ptrVec.emplace_back(arr3);
	ptrVec.emplace_back(arr4);
	ptrVec.emplace_back(arr5);
	ptrVec.emplace_back(arr6);
	auto p = MegerSort(ptrVec, 0, ptrVec.size()-1);
	for (int i = 0; i < p.second - 1; ++i)
	{
		cout << p.first[i] << " ";
	}
	delete[] p.first;
	return 0;
}
